In an ad hoc wireless network, transceivers or “nodes” are arranged to communicate with each other without any network infrastructure or centralized administration. The arrangement can be static or dynamic, or combinations thereof. The nodes can be cellular telephones, portable computing devices, or special purpose devices such as sensors. The nodes in the network establish routing among themselves to form their own network. Due to a limited transmission range of the transceivers, messages from a source node may have to pass through one or more intermediate routing nodes before reaching a destination node.
In many ad hoc wireless networks, most, if not all of the nodes are battery powered. Therefore, minimizing power consumption is a primary concern because nodes become disabled when they deplete the power stored in their batteries. The loss of a node is a serious problem. First, the node cannot perform its assigned task. Second, the node can no longer act as a router for other nodes. Thus, the loss of a node can partition the network. Therefore, it is desired to prolong the life of battery operated nodes in a network.
Some techniques for reducing power decrease transcoder complexities, use low power circuits and low signaling-cost routing protocols. Other techniques attempt to exploit the network topology to reduce power.
Heinzelman et al., in “Energy-efficient Communication Protocol for Wireless Micro-sensor Networks,” Proc. of the IEEE Hawaii Int. Conf. on System Sciences, pp. 3005-3014, January, 2000, describe communication protocols for power reduction in a wireless network. They describe a clustering based protocol that utilizes randomized rotation of local cluster heads to evenly distribute the power load among the nodes in the network. They also indicate that when the distance between two nodes is short, direct transmission is more efficient than multiple hop transmission.
Chang et al, in “Energy Conserving Routing in Wireless Ad-hoc Networks,” Proc. of IEEE INFOCOM 2000, March, 2000, describe methods for selecting routes and corresponding power levels in a static wireless network so that power consumption is reduced.
Catovic et al, in “A new approach to minimum energy routing for next generation multi-hop wireless networks,” Journal of Communications and Networks, Special Issue on “Evolving from 3G deployment to 4G definition,” December 2002, describe a technique for transmitting data over two different channels at different power levels. A rake receiver is used to reconstruct the original data by combining the two received signals.
Chen et al., “Energy Efficient System Design with Optimum Transmission Range for Wireless Ad-hoc Networks,” Proc of IEEE Int. Conf. on Communications, ICC'02, pp. 945-952, May, 2002, determine optimum transmission range and hop distances in wireless ad-hoc networks.
In many wireless networks, information is exchanged with packets. When nodes are within radio range, the nodes communicate directly with each other, otherwise the nodes communication indirectly by a series of wireless ‘hops’ or links through other intermediate nodes. The end-to-end links between a source node and a destination node are known as a route.
Therefore, it is necessary for nodes to locate neighboring nodes that are within radio range, and to determine routes to other nodes. For time sensitive data, e.g., sensor data, or for streaming data, e.g., audio or video streams, it is necessary to find a route with a minimum amount of delay. For battery-powered networks, it is also necessary to find routes that include nodes with sufficient power reserves.
In some ad-hoc networks, the nodes can be mobile while exchanging data. Therefore, the routing information needs to be updated dynamically and on-demand. It is desired to do this while minimizing traffic, minimizing the computational load, minimizing memory requirements, and minimizing power consumption.
In the prior art, two techniques have been used to address the above problems: dynamic source routing (DSR), and ad-hoc on-demand distance vector routing (AODV).
DSR is ‘on-demand’. DSR allows a source node to discover dynamically a route, via multiple network links, to any destination node in the ad-hoc network. DSR is also ‘loop-free’ because each packet includes a complete, ordered list of addresses of nodes that form the route.
DSR operates in two modes: route discovery, and route maintenance. During route discovery, the source node discovers and determines an ordered list of nodes through which packets must pass while traveling to the destination node. This ordered list is appended to each packet that is transmitted in the network. In that way, an intermediate node merely forwards a received packet to the next node in the ordered list. Thus, intermediate nodes do not need to discover and maintain routing information for all nodes in the network. However, the intermediate node can store the routing information contained in forwarded packets in a memory for future use.
AODV is also on-demand and supports multicast. However, in this case, each node in the network maintains a routing table. Therefore, the memory requirements are potentially higher for this technique than for DSR. For local connectivity, each node sends periodic ‘hello’ packets to neighboring nodes. AODV invalidates idle routes after a predetermined amount. In high mobility environments, AODV has less delay than DSR. However, because the overhead associated with the hello packets in AODV is high, the throughput of AODV is less than DSR.